#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

// 使用STL队列
void queueSTLDemo() {
    cout << "=== STL队列演示 ===" << endl;
    
    queue<int> q;
    
    // 入队
    cout << "入队操作:" << endl;
    q.push(1);
    cout << "入队: 1" << endl;
    q.push(2);
    cout << "入队: 2" << endl;
    q.push(3);
    cout << "入队: 3" << endl;
    
    // 查看队首和队尾元素
    cout << "队首元素: " << q.front() << endl;
    cout << "队尾元素: " << q.back() << endl;
    
    // 出队
    cout << "出队操作:" << endl;
    q.pop();
    cout << "出队后队首元素: " << q.front() << endl;
    
    // 队列大小
    cout << "当前队列大小: " << q.size() << endl;
    
    // 判断队列是否为空
    cout << "队列是否为空: " << (q.empty() ? "是" : "否") << endl;
    
    // 继续出队
    q.pop();
    cout << "再次出队后队首元素: " << q.front() << endl;
    q.pop();
    cout << "最后出队后队列是否为空: " << (q.empty() ? "是" : "否") << endl;
}

// 自定义队列实现
class CustomQueue {
private:
    int* arr;
    int capacity;
    int frontIndex;
    int rearIndex;
    int count;

public:
    CustomQueue(int size) {
        capacity = size;
        arr = new int[capacity];
        frontIndex = 0;
        rearIndex = -1;
        count = 0;
    }
    
    ~CustomQueue() {
        delete[] arr;
    }
    
    void enqueue(int value) {
        if(count >= capacity) {
            cout << "队列已满! 无法入队 " << value << endl;
            return;
        }
        rearIndex = (rearIndex + 1) % capacity;
        arr[rearIndex] = value;
        count++;
        cout << "入队: " << value << endl;
    }
    
    void dequeue() {
        if(count <= 0) {
            cout << "队列为空! 无法出队" << endl;
            return;
        }
        cout << "出队: " << arr[frontIndex] << endl;
        frontIndex = (frontIndex + 1) % capacity;
        count--;
    }
    
    int front() {
        if(count <= 0) {
            cout << "队列为空!" << endl;
            return -1;
        }
        return arr[frontIndex];
    }
    
    int rear() {
        if(count <= 0) {
            cout << "队列为空!" << endl;
            return -1;
        }
        return arr[rearIndex];
    }
    
    int size() {
        return count;
    }
    
    bool empty() {
        return count == 0;
    }
    
    void display() {
        if(empty()) {
            cout << "队列为空" << endl;
            return;
        }
        cout << "队列内容 (从队首到队尾): ";
        for(int i = 0; i < count; i++) {
            int index = (frontIndex + i) % capacity;
            cout << arr[index] << " ";
        }
        cout << endl;
    }
};

void customQueueDemo() {
    cout << "\n=== 自定义队列演示 ===" << endl;
    
    CustomQueue q(5);
    
    cout << "初始状态: ";
    q.display();
    
    // 入队操作
    cout << "\n入队操作:" << endl;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();
    
    // 查看队首和队尾
    cout << "队首元素: " << q.front() << endl;
    cout << "队尾元素: " << q.rear() << endl;
    
    // 出队操作
    cout << "\n出队操作:" << endl;
    q.dequeue();
    q.display();
    
    cout << "队首元素: " << q.front() << endl;
    
    // 继续操作
    q.enqueue(40);
    q.enqueue(50);
    q.enqueue(60); // 这会触发队列满警告
    q.display();
}

// 双端队列 (Deque) 演示
void dequeDemo() {
    cout << "\n=== 双端队列演示 ===" << endl;
    
    deque<int> dq;
    
    // 从两端插入
    cout << "从两端插入元素:" << endl;
    dq.push_back(1);  // 尾部插入
    cout << "尾部插入: 1" << endl;
    dq.push_front(2); // 头部插入
    cout << "头部插入: 2" << endl;
    dq.push_back(3);
    cout << "尾部插入: 3" << endl;
    dq.push_front(4);
    cout << "头部插入: 4" << endl;
    
    // 显示队列内容
    cout << "双端队列内容: ";
    for(int i = 0; i < dq.size(); i++) {
        cout << dq[i] << " ";
    }
    cout << endl;
    
    // 从两端访问
    cout << "头部元素: " << dq.front() << endl;
    cout << "尾部元素: " << dq.back() << endl;
    
    // 从两端删除
    cout << "从两端删除元素:" << endl;
    dq.pop_front(); // 删除头部
    cout << "删除头部后: ";
    for(int i = 0; i < dq.size(); i++) {
        cout << dq[i] << " ";
    }
    cout << endl;
    
    dq.pop_back();  // 删除尾部
    cout << "删除尾部后: ";
    for(int i = 0; i < dq.size(); i++) {
        cout << dq[i] << " ";
    }
    cout << endl;
}

// 队列的应用：广度优先搜索（BFS）示例
void bfsDemo() {
    cout << "\n=== BFS演示（简单版本）===" << endl;
    
    // 简单的图：邻接表表示
    vector<vector<int>> graph = {
        {1, 2},     // 节点0连接到节点1和2
        {0, 3, 4},  // 节点1连接到节点0, 3, 4
        {0, 5},     // 节点2连接到节点0, 5
        {1},        // 节点3连接到节点1
        {1},        // 节点4连接到节点1
        {2}         // 节点5连接到节点2
    };
    
    int start = 0;
    vector<bool> visited(6, false);
    queue<int> q;
    
    cout << "从节点 " << start << " 开始的BFS遍历:" << endl;
    
    q.push(start);
    visited[start] = true;
    
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        cout << "访问节点: " << current << endl;
        
        // 访问所有相邻节点
        for(int neighbor : graph[current]) {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
                cout << "  发现未访问节点: " << neighbor << endl;
            }
        }
    }
}

// 队列的应用：任务调度模拟
void taskSchedulingDemo() {
    cout << "\n=== 任务调度模拟 ===" << endl;
    
    queue<string> taskQueue;
    
    // 添加任务
    taskQueue.push("任务A");
    taskQueue.push("任务B");
    taskQueue.push("任务C");
    taskQueue.push("任务D");
    
    cout << "初始任务队列大小: " << taskQueue.size() << endl;
    
    // 模拟任务执行
    int timeSlice = 1; // 时间片
    while(!taskQueue.empty()) {
        string currentTask = taskQueue.front();
        taskQueue.pop();
        
        cout << "时间片 " << timeSlice << ": 执行 " << currentTask << endl;
        timeSlice++;
        
        // 模拟某些任务可能需要重新排队
        if(currentTask == "任务B") {
            taskQueue.push("任务B-重试");
            cout << "  任务B需要重试，重新加入队列" << endl;
        }
    }
    
    cout << "所有任务执行完毕" << endl;
}

// 优先队列演示
void priorityQueueDemo() {
    cout << "\n=== 优先队列演示 ===" << endl;
    
    priority_queue<int> pq; // 默认最大堆
    
    cout << "插入元素: 3, 1, 4, 1, 5" << endl;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    
    cout << "优先队列内容 (按优先级出队): ";
    while(!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    
    // 最小堆示例
    cout << "\n最小堆示例:" << endl;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    cout << "插入相同元素到最小堆: 3, 1, 4, 1, 5" << endl;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(1);
    minHeap.push(5);
    
    cout << "最小堆内容 (按优先级出队): ";
    while(!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;
}

// ================ 竞赛常用写法 ================

// 竞赛推荐：deque（比queue更强大）
void dequeContestDemo() {
    cout << "\n=== 竞赛常用：deque演示 ===" << endl;
    
    deque<int> dq;
    
    // 两端操作
    dq.push_back(1);   // 尾部插入
    dq.push_front(2);  // 头部插入
    dq.push_back(3);
    dq.push_front(4);
    
    cout << "deque内容: ";
    for(int x : dq) cout << x << " ";
    cout << endl;
    
    cout << "头部: " << dq.front() << ", 尾部: " << dq.back() << endl;
    
    // 两端删除
    dq.pop_front();
    dq.pop_back();
    
    cout << "删除后: ";
    for(int x : dq) cout << x << " ";
    cout << endl;
}

// 竞赛常用：priority_queue（堆）
void priorityQueueContestDemo() {
    cout << "\n=== 竞赛常用：priority_queue演示 ===" << endl;
    
    // 最大堆（默认）
    priority_queue<int> maxHeap;
    
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    for(int x : nums) {
        maxHeap.push(x);
    }
    
    cout << "最大堆（降序）: ";
    while(!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;
    
    // 最小堆
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for(int x : nums) {
        minHeap.push(x);
    }
    
    cout << "最小堆（升序）: ";
    while(!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;
}

// 竞赛常见：BFS模板
void bfsContestTemplate(const vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    cout << "BFS遍历顺序: ";
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        for(int neighbor : graph[node]) {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    cout << endl;
}

// 竞赛常见：滑动窗口最大值（单调队列）
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    deque<int> dq;  // 存储索引，保持单调递减
    vector<int> result;
    
    for(int i = 0; i < nums.size(); i++) {
        // 移除超出窗口的元素
        while(!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        
        // 移除小于当前元素的元素
        while(!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 窗口形成后记录最大值
        if(i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

// 竞赛常见：Dijkstra算法（优先队列）
void dijkstraDemo(const vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while(!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if(d > dist[u]) continue;
        
        for(auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            
            if(dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    cout << "从节点 " << start << " 到各节点的最短距离:" << endl;
    for(int i = 0; i < n; i++) {
        cout << "到节点 " << i << ": " << dist[i] << endl;
    }
}

// 竞赛技巧：用vector模拟队列
void vectorAsQueueDemo() {
    cout << "\n=== 竞赛技巧：vector模拟队列 ===" << endl;
    
    vector<int> q;
    
    // 入队
    for(int i = 1; i <= 3; i++) {
        q.push_back(i);
        cout << "入队: " << i << endl;
    }
    
    // 出队
    while(!q.empty()) {
        cout << "出队: " << q.front() << endl;
        q.erase(q.begin());
    }
}

int main() {
    // 传统队列演示
    queueSTLDemo();
    customQueueDemo();
    dequeDemo();
    bfsDemo();
    taskSchedulingDemo();
    priorityQueueDemo();
    
    // 竞赛常用写法
    dequeContestDemo();
    priorityQueueContestDemo();
    vectorAsQueueDemo();
    
    // 竞赛常见应用
    cout << "\n=== 竞赛常见应用 ===" << endl;
    
    // BFS模板
    vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}};
    bfsContestTemplate(graph, 0);
    
    // 滑动窗口最大值
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> windowMax = maxSlidingWindow(nums, k);
    cout << "滑动窗口最大值: ";
    for(int x : windowMax) cout << x << " ";
    cout << endl;
    
    // Dijkstra算法
    vector<vector<pair<int, int>>> weightedGraph = {
        {{1, 4}, {2, 2}},
        {{0, 4}, {2, 1}, {3, 5}},
        {{0, 2}, {1, 1}, {3, 8}},
        {{1, 5}, {2, 8}}
    };
    dijkstraDemo(weightedGraph, 0);
    
    cout << "\n=== 竞赛选择指南 ===" << endl;
    cout << "1. 普通队列：使用 queue<T>" << endl;
    cout << "2. 双端操作：使用 deque<T>（推荐）" << endl;
    cout << "3. 优先队列：使用 priority_queue<T>" << endl;
    cout << "4. BFS遍历：queue<int>" << endl;
    cout << "5. 滑动窗口：deque<int>" << endl;
    cout << "6. 最短路径：priority_queue<pair<int,int>>" << endl;
    
    cout << "\n=== 队列的应用场景 ===" << endl;
    cout << "1. 任务调度" << endl;
    cout << "2. 消息队列" << endl;
    cout << "3. 广度优先搜索(BFS)" << endl;
    cout << "4. 打印任务队列" << endl;
    cout << "5. 缓冲区管理" << endl;
    cout << "6. 网络数据包处理" << endl;
    
    return 0;
}
